/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年01月06日
*   描    述：
*
================================================================*/

/*
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 *
 * 示例 1：
 *   输入：nums = [1,2,0]
 *   输出：3
 *
 * 示例 2：
 *   输入：nums = [3,4,-1,1]
 *   输出：2
 *
 * 示例 3：
 *   输入：nums = [7,8,9,11,12]
 *   输出：1
 *
 * 提示：
 *   1 <= nums.length <= 5 * 105
 *   -231 <= nums[i] <= 231 - 1
 */

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
  int key;
  void *value;
  struct Node *next;
} Node;

typedef struct Map {
  Node **buckets;
  int size;
} Map;

// 创建一个新的节点
Node *createNode(int key, void *value) {
  Node *node = (Node *)malloc(sizeof(Node));
  if (node == NULL) {
    perror("Error: unable to allocate memory for new node.");
    exit(EXIT_FAILURE);
  }
  node->key = key;
  node->value = value;
  node->next = NULL;
  return node;
}

// 删除一个节点
void deleteNode(Node *node) { free(node); }

// 计算哈希值
int hash(int key, int size) {
  int hash = 0;
  hash = 31 * hash + key;
  return abs(hash % size);
}

// 创建一个新的 Map
Map *CreateMap(int size) {
  Map *map = (Map *)malloc(sizeof(Map));
  if (map == NULL) {
    perror("Error: unable to allocate memory for new map.");
    exit(EXIT_FAILURE);
  }
  map->size = size;
  map->buckets = (Node **)calloc(size, sizeof(Node *));
  if (map->buckets == NULL) {
    perror("Error: unable to allocate memory for buckets.");
    exit(EXIT_FAILURE);
  }
  return map;
}

// 删除一个 Map
void DeleteMap(Map *map) {
  int i = 0;
  for (; i < map->size; ++i) {
    Node *node = map->buckets[i];
    while (node != NULL) {
      Node *tmp = node;
      node = node->next;
      deleteNode(tmp);
    }
  }
  free(map->buckets);
  free(map);
}

// 添加键值对
void Put(Map *map, int key, void *value) {
  int idx = hash(key, map->size);
  Node *node = map->buckets[idx];
  while (node != NULL) {
    if (node->key == key) {
      node->value = value;
      return;
    }
    node = node->next;
  }
  node = createNode(key, value);
  node->next = map->buckets[idx];
  map->buckets[idx] = node;
}

// 获取键对应的值，如果不存在则返回 NULL
void *Get(Map *map, int key) {
  int idx = hash(key, map->size);
  Node *node = map->buckets[idx];
  while (node != NULL) {
    if (node->key == key) return node->value;
    node = node->next;
  }
  return NULL;
}

int firstMissingPositive(int *nums, int numsSize) {
  Map *_map = CreateMap(500000);
  for (int i = 0; i < numsSize; i++) {
    if (nums[i] > 0) {
      Put(_map, nums[i], nums + i);
    }
  }
  int j = 0;
  while (1) {
    j++;
    if (Get(_map, j) == NULL) {
      break;
    }
  }
  DeleteMap(_map);
  return j;
}

int main() {
  int nums[] = {1, 2, 0};
  int ret = firstMissingPositive(nums, sizeof(nums) / sizeof(nums[0]));
  printf("%d\n", ret);
  return 0;
}